// https://www.lintcode.com/problem/reorder-list/

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: nothing
     */
    public void reorderList(ListNode head) {
        // write your code here
        /*
        0->1->2->3->4->5 (n = 5) => 0->5->1->4->2->3 (012/543)
        0->1->2->3->4->5->6 (n = 6) => 0->6->1->5->2->4->3 (0123/654)        
        */
        if (head != null) {
            ListNode one = head;
            ListNode two = head;
            while ((one != null) && (two != null)) {
                two = two.next;
                if (two != null) {
                    two = two.next;
                    one = one.next;
                } else {
                    break;
                }
            }
            two = one.next;
            one.next = null;
            ListNode newHead = reverse(two);
            while (head != null) {
                if (newHead != null) {
                    ListNode _next = head.next;
                    head.next = newHead;
                    newHead = newHead.next;
                    head.next.next = _next;
                    head = _next;
                } else {
                    head = head.next;
                }
            }
        }
    }

    protected ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode newHead = null;
        while (head != null) {
            ListNode node = head;
            head = head.next;
            node.next = newHead;
            newHead = node;
        }
        return newHead;
    }
}